CPPSTL总览(一)之序列容器

我想很多从别的高级语言转过来刚接触C++的时候一定会觉得C++贼不好用,最简单的数据类型,比如动态数组、字典都没有,这样在日常开发中使用起来十分麻烦,那是因为大家还没有接触到C++的STL(standard template library)标准模板库,是建立在基础数据结构基础上的实现的包含数据容器、迭代器、算法等强大的组件库。

这篇文章主要是全面的给大家分享一下STL序列容器总的一些知识,让大家有一个简单的了解,本文并没有详细的用法描述,所谓序列容器就是在这个容器中的所有数据是有前后顺序的。下面就让我们来看一下序列容器都有哪些吧:

array

array(数组容器)起作用与数组并无差别,都是在内存上开辟一块内存连续的内存区存储固定大小的数据,数据不能增加也不能删除。

但是array有一个好处就是它可以做越界检查,另外array提供了很好的正反向迭代器。这是普通数组不具备的。array在用at()方法访问元素时会做安全检查,所以一般建议用at()访问:

vector

vector(向量容器)是一个长度可变的序列,它与array和数组的区别在:vector属于变长的容器,即可以根据数据的插入和删除重新构造容器容量;但是array和数组属于定长容器。vector与array一样都可以用下标和at()访问,同样at()也支持越界检查。

vector可以利用emplace、erase、swap、push_back/pop_back配合迭代器来实现在任意位置插入和删除元素,但是用起来会跟麻烦,新手可能会有点难理解:

deque

deque(双向队列容器)是一个长度可变的、可以自动增长的序列。它的访问操作和vector很相似,但是内部的存储方式和 vector 不同。它组织元素的方式导致容器的大小总是和容量相等,同样因为 deque 内部组织元素的方式不同,deque 的操作和 vector 相比要慢。

deque通常由一些独立的区块组成,第一个区块朝某方向发展,最后一个区块朝另一个方向发展。它允许较为快速地随机访问但它不像vector一样把所有对象保存在一个连续的内存块,而是多个连续的内存块。并且在一个映射结构中保存对这些块以及顺序的跟踪。

deque在日常开发中用的不多,因为他的功能都可以用vector和list代替,并且它的效率不高,它唯一的优势是头部插入效率较vector和list高。它最主要的作用还是作为栈和队列的底层实现存在。

List

List它的底层是双向链表实现的(双向链表我之前的文章中已经有很详细的讲解了,大家感兴趣的可以去看一下),在这个序列的任何地方都可以高效地增加或删除元素。访问容器中任意元素的速度要比前三种容器慢,这是因为 list 必须从第一个元素或最后一个元素开始访问,需要沿着链表移动,直到到达想要的元素,而上面讲的几种容器都是可以随机访问的,所以在访问效率上List是有不足的,但是List的有点在与他的物理内存不连续,在增删元素时不需要大量的移动后续的元素,所以他的增删效率是最高的。

如上所示,由于List存储物理结构为不连续,所以在增删时只需要操作对应节点的前后指针就可以了。但是他在访问元素时必须从头或者从尾开始一直遍历过去。

forward_list

forward_list它的底层就是单链表,它跟List的区别就是节点没有指向前一个节点的指针即before指针,所以他只能从前往后访问不能从后往前。它跟List操作上的区别就是所有List从后往前的操作在forward_list上都是行不通的,比如在一个节点前面插入节点、反向迭代等。

但是它的操作效率是比List要高的,因为毕竟少一个节点少一步操作嘛,所以大家在后续开发中,如果不牵涉到从后往前的的需求,可以用forward_list。

本页共31段,1837个字符,4350 Byte(字节)